package algorithm.leetcode.I101to200;

import algorithm.leetcode.ListNode;

/**
 * 类似归并排序
 */

public class Q148 {

    public ListNode sortList(ListNode head) {
        // base case
        if (head == null || head.next ==  null) return head;

        // 若链表长为2n,则slow指向第n个,若长2n-1则指向第n个,即前一半总比后一半多1个或者相等,slow指向前一半的末尾
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 递归排序前一半和后一半
        // 断开slow和后面的联系,取得后半段的头部
        ListNode later = slow.next;
        slow.next = null;
        ListNode former = sortList(head);
        later = sortList(later);

        // 合并两段链表
        ListNode fakeHead = new ListNode(-12391);
        ListNode curr = fakeHead;

        while (later != null || former != null) {
            if (later != null && former != null) {
                if (later.val < former.val) { curr.next = later;  later = later.next; }
                else { curr.next = former; former = former.next; }
            }
            else if (later != null) { curr.next = later;  later = later.next; }
            else { curr.next = former; former = former.next; }
            curr = curr.next;
        }

        // 返回结果
        return fakeHead.next;
    }

}
